1. Field of the Invention
The present invention relates generally to the field of priority control, and more specifically to controlling the priority accorded to more than one queue seeking access to a shared resource.
2. Description of the Related Art
Data communication networks receive and transmit ever increasing amounts of data. Data is transmitted from an originating entity or requester, through the network to a destination, such as a channel or resource. Along this path may be multiple points that receive data, typically in the form of packets or data frames, and along each point data must be routed to the next point in the network in a rapid and efficient manner. Certain protocols or standards may be employed in transferring data from one point to another, and such standards enable hardware and software employing different configurations to effectively receive and transfer the data. Such standards include, but are not limited to, Utopia, X.25, and other standards promulgated by the ITU and ANSI.
The points throughout the data network operate to receive data requests or packets from various requesters and provide results or satisfy requests in an orderly and efficient manner. Requests may arrive synchronously or asynchronously, and requests may be for access to multiple resources or channels or to particular sets of resources or channels. A single requester may request access to multiple resources at one time. The hardware or software at the data transmission point in the data network acts as a traffic officer, deciding which data packets receive priority in transmission while requiring others to wait.
The traditional hardware or software used to perform this access control function has been a form of arbiter. Other designs have been employed, including lookup tables, FIFO arrangements, and other designs known to those skilled in the art. An arbiter receives requests from requesters and allocates those requests among the channels or resources sequentially according to requester position. For example, if requestors one through five seek access to a Channel A, and requesters one through four transmit multiple requests while requester five transmits one request, the arbiter allows access in an ordered manner to requesters one through five and subsequently to one through four until all requests have been satisfied. If requester five has not made a request, the arbiter skips requester five and goes on to the next requester in sequence. If requester five adds a request at some point during arbitration, this new request is satisfied sequentially. This is sometimes referred to as round robin arbitration. Arbitration differs from a FIFO arrangement in that input channels are individually queued in arbitration, while FIFO employs a single queue, and the first request received from any requester is the first request satisfied.
The problems with previous arbitration and FIFO arrangements include a general inability to prioritize the arriving requests in a predetermined ratio, such as permitting channel one to have access to 75 percent of the resource while permitting channel two only 25 percent of the resource. It is desirable for certain requests, requesters, or channels to receive higher priority or greater access to the resource than others. Previous arbitration schemes simply go through the requests from the requesters in order and allow them access to the resource when a request is present and when it is the requestor's “turn.” FIFO arrangements cycle through the requests as received with no allowance for priority or ratio of access to the resource. In the previous arbitration arrangement, using the foregoing example, if requester one is to be accorded 25 percent of the accesses to the resource but generates a large number of requests in a short amount of time, while requester two is to be accorded 75 percent of the accesses, the previous arbitration scheme will grant the request from requester one any time the requester one queue includes a request. A FIFO will simply grant access based on order received with no regard to the desired ratio. This granting of a slot to undesirable requests based on the desired ratio hinders system performance by slowing desirable requests. The result is delays to satisfy requests, lower throughput, or incorrect ratio throughput at the data transfer point.
While arbiters and FIFOs are simple, straightforward, and relatively well known, it would be desirable to offer a simple, straightforward mechanism or method that provides for statistical control, such as controlling ratio, between queues using relatively well known devices.